import sys
import math
	
bin = lambda x,size: ''.join(x & (1 << i) and '1' or '0' for i in range(size, -1,-1))

#generalized to any hard vector size
def buildTable(hardVector):
	possibilities = {}

	for i in range(2**len(hardVector)):
		sum = 0
		for j in range(len(hardVector)):
			if i & 2**j:
				sum += hardVector[j]
		if not possibilities.has_key(sum):
			possibilities[sum] = i
		else:
			if type(possibilities[sum]) == type([]):
				possibilities[sum].append(i)
			else:
				possibilities[sum] = [possibilities[sum], i]
	
	return possibilities
	
#generalized
def parseCipherText(filename):
	file = open(filename, 'r')
	cipher = [int(elem) for elem in file.read().split()]
	file.close()
	return cipher

#generalized
def parseHardVector(filename):
	file = open(filename, 'r')
	hard = [int(line) for line in file]
	file.close()
	return hard

#generalized
def genMask(ones, zeros = 0):
	mask = 0
	for i in range(ones):
		mask += 1
		mask = mask << 1
	
	for i in range(zeros):
		mask = mask << 1
	
	return mask
	
#generalized
def getCharsFromNum(num, size, previous = None, numLeft = 0):
	if previous != None:
		num += previous << size
		size += numLeft

	#need to shift off 8 bits at a time and get the character representation
	left = size % 8
	chars = int(math.floor(size/8))
	#get the left over bits as an integer
	numLeft = num & genMask(left)
	
	num = num >> left
	
	#generate an 8 bit mask which will mask the lower 8 bits
	#mask = genMask(8)
	mask = 0xFF
	
	#generates all the individual characters of the string
	#seq = [chr((num >> i*8) & mask) for i in range(chars)]
	
	return ''.join([chr((num >> (i*8)) & mask) for i in range(chars)]), numLeft, left
	
			

#generalized
def printText(possibilities, cipherText, size, hardVec , stream = sys.stdout):
	lBits = 0
	lNum  = 0
	for elem in cipherText:
		print "%d is key? - %s" % (elem, str(possibilities.has_key(elem)))
		if possibilities.has_key(elem):
			
			key = possibilities[elem]
			
			if type(key) != type([]):
				chars, lNum, lBits = getCharsFromNum(key, size, lNum, lBits)
				stream.write(chars)
			else:
				print "something is wrong"
				#in this case there are multiple possibilities for the characters
				#we need to try and determine the best sequence and print it out.
				#if multiple sequences are good.  This currently does nothing in the event
				#of a tie.  It just does the dumb thing and prints out everything
				stream.write('[' + ', '.join([getCharsFromNum(num, size, lNum, lBits)[0] for num in key]) + ']')
				lBits = (size + lBits) % 8
				lNum = elem & genMask(lBits)
		else:
			for i in range(2**size):
				sum = 0
				for j in range(size):
					if i & 2**j:
						sum += hardVec[j]
				if sum == elem:
					print "%d - %d" % (elem, i)
def main():
	cipher = []
	hard = []
	alphabet = []
	try:
		cipher_filename = raw_input("Enter the name of a file with the knapsack cipher text:  ")
		cipher = parseCipherText(cipher_filename)
		
		hard_filename = raw_input("Enter the name of the file containing the hard vector:  ")
		hard = parseHardVector(hard_filename)
		
		#alpha_filename = raw_input("Enter the name of the file containing the alphabet:  ")
		#alpha = parseAlpha(alpha_filename)
	except IOError (errno, strerror):
		print "I/O error({0}): {1}".format(errno,strerror)
		sys.exit(-1)
		
	possibilities = buildTable(hard)
	
	try:
		output_filename = raw_input("Enter the name of a file to output the text to:  ")
		f = open(output_filename, 'w')
		printText(possibilities, cipher, len(hard),hard, f)
		f.close()
	except:
		print "exception occured"
		printText(possibilities, cipher, len(hard), hard)
	
	
if __name__ == '__main__':
	main()
	
